public class HashBucket {
    private static class Node {
        private int key;
        private int val;
        private Node next;

        public Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }

    private Node[] array;
    private int usedSize;
    private static final double loadFactor = 0.75;//负载因子

    public HashBucket() {
        this.array = new Node[10];
        this.usedSize = 0;
    }

    public void put(int key,int val) {
        int index = key%this.array.length;
        //判断index位置key是否存在
        Node cur = this.array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //头插法
        Node node = new Node(key,val);
        node.next = this.array[index];
        this.array[index] = node;
        this.usedSize++;
        //大于负载因子就扩容
        if (loadFactor() >= loadFactor) {
            resize();
        }
    }
    public double loadFactor() {
        return this.usedSize*1.0 / this.array.length;
    }
    public void resize() {
        //二倍扩容
        Node[] arr = new Node[this.array.length*2];
        //遍历原来的哈希桶,重新哈希
        for (int i = 0; i < this.array.length; i++) {
            Node cur = this.array[i];
            Node curNext = null;//记录cur.next
            while (cur != null) {
                curNext = cur.next;
                int index = cur.key%arr.length;
                cur.next = arr[index];
                arr[index] = cur;
                cur = curNext;
            }
        }
        this.array = arr;
    }
    public int get(int key) {
        //怎么存就怎么取
        if (this.usedSize == 0) {
            throw new NullPointerException("哈希表为空");
        }
        int index = key%this.array.length;
        Node cur = this.array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        //不考虑-1，没找到直接返回-1
        return -1;
    }
}
